L2-022 重排链表

题目 L2-022 重排链表

image-129349ef

思路分析

哈希模拟链表 保存原序和处理后顺序

代码实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using Pll = pair<ll, ll>;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
const int inf = 0x3f3f3f3f;

unordered_map<int, PII> node;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int head, n;
    cin >> head >> n;

    while (n--) {
        int addr, val, nxt;
        cin >> addr >> val >> nxt;
        node[addr] = {val, nxt};
    }

    vector<int> order;
    for (int i = head; i != -1; i = node[i].second) {
        order.push_back(i);
    }

    vector<int> result;
    int l = 0, r = order.size() - 1;
    while (l <= r) {
        if (r != l) result.push_back(order[r--]);
        result.push_back(order[l++]);
    }

    for (int i = 0; i < result.size(); ++i) {
        int addr = result[i];
        int nxt = (i + 1 < result.size()) ? result[i + 1] : -1;
        printf("%05d %d ", addr, node[addr].first);
        if (nxt == -1) printf("-1\n");
        else printf("%05d\n", nxt);
    }

    return 0;
}

同类题型

视频讲解

⬅️ L2-021 点赞狂魔 🏠 00-天梯赛 ➡️ L2-023 图着色问题